Bisection Algorithm

Pronunciation: /baɪˈsɛkt.ʃən ˈæl.gəˌrɪð.əm/ Explain

The bisection algorithm is a method for approximating the root of an equation by successively bisecting an interval that contains the root. The root of a function f(x) is where the function equals zero: f(x) = 0. If two values of f(x) are known, and one is positive and the other negative, the Intermediate Value Theorem guarantees that a root exists between those two values if f(x) is continuous on the interval. The bisection algorithm approximates that root to as many significant digits as one wants.

The basic algorithm starts with a closed interval [a..b] where the sign of f(a) is the opposite of the sign of f(b) (if f(a)>0 then f(b)<0, and if f(a)<0 then f(b)>0). The middle value of the interval is found by averaging the endpoints: . The value of f(m) is calculated. If it is negative, replace the endpoint of the interval for which f(x) is negative with m. If it is positive, replace the endpoint of the interval for which f(x) is positive with m. Then repeat the algorithm until sufficient significant digits have been found.

Example 1

Calculate the root of f(x) = x² - 2 that lies between 1 and 2 to two significant digits. Since f(1)=-1 and f(2) = 2, let a=1 and b=2;

Iteration	a	b	m=(a+b/2)	f(m)	Discussion
1	1	2	(1+2)/2 = 1.5	f(1.5) = 0.25	Since 0.25 > 0, substitute 1.5 for 2. The new interval is [1,1.5].
2	1	1.5	(1+1.5)/2 = 1.25	f(1.25) = -0.4375	Since -0.4375 < 0, substitute 1.25 for 1. The new interval is [1.25,1.5].
3	1.25	1.5	(1.25+1.5)/2 = 1.375	f(1.375) = -0.109375	Since -0.109375 < 0, substitute 1.375 for 1.25. The new interval is [1.375,1.5].
4	1.375	1.5	(1.375+1.5)/2 = 1.4375	f(1.4375) = 0.06640625	Since 0.06640625 > 0, substitute 1.4375 for 1.5. The new interval is [1.375,1.4375].
5	1.375	1.4375	(1.375+1.4375)/2 = 1.40625	f(1.40625) = -0.0224609375	Since -0.0224609375 < 0, substitute 1.40625 for 1.375. The new interval is [1.40625,1.4375]. Since the endpoints of the interval round to the same two digit number, the answer is 1.4.
Table 1: Example 1 of the bisection algorithm

References

1. McAdams, David E.. All Math Words Dictionary, bisection algorithm. 2nd Classroom edition 20150108-4799968. pg 27. Life is a Story Problem LLC. January 8, 2015. Buy the book

Cite this article as:

McAdams, David E. Bisection Algorithm. 4/12/2019. All Math Words Encyclopedia. Life is a Story Problem LLC. https://www.allmathwords.org/en/b/bisectionalgorithm.html.

Image Credits

• All images and manipulatives are by David McAdams unless otherwise stated. All images by David McAdams are Copyright © Life is a Story Problem LLC and are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Revision History

4/12/2019: Changed equations and expressions to new format. (McAdams, David E.)
1/29/2019: Fixed page formatting issues. (McAdams, David E.)
12/21/2018: Reviewed and corrected IPA pronunication. (McAdams, David E.)
6/22/2018: Removed broken links, updated license, implemented new markup. (McAdams, David E.)
5/5/2011: Initial version. (McAdams, David E.)